The invention relates generally to halftoning techniques and more particularly to an error diffusion halftoning technique.
Digital images provide a convenient format for transmission, modification, and/or reproduction of images. When an image is captured digitally, grayscale information for each pixel of an image is extracted. Typically, 256 grayscale levels are utilized to extract the grayscale information. However, the majority of printers that are currently in use are binary with respect to their printing methods. That is, the printers operate to reproduce the original image either by depositing or by refraining to deposit a small amount of ink or toner for each pixel of the captured image. The binary nature of these printers allows only two levels of grayscale to be printed for each pixel. Thus, digitally captured images having more than two levels of grayscale cannot be reproduced by the binary printers, unless a special printing technique, such as halftoning, is utilized.
A halftoning technique is a process for printing different shades of grayscale by varying the density of xe2x80x9cdarkxe2x80x9d pixels that have been deposited with ink or toner. A lower density of dark pixels equates to a lighter shade of grayscale, while a higher density of dark pixels equates to a darker shade of grayscale. Since the density of dark pixels can vary in numerous degrees, the number of grayscales that can be produced using the halftoning technique is far greater than two levels. As long as the pixels are sufficiently small, the individual dark pixels will not be apparent to a viewer. Instead, the viewer will see smooth areas having different shades of grayscale, which are directly related to the density of dark pixels.
A common type of halftoning technique is known as xe2x80x9can error diffusion halftoning technique.xe2x80x9d In error diffusion halftoning, a halftoning error associated with a generated halftone signal for each pixel of a digital image is distributed among neighboring pixels in order to determine which pixel should be deposited with ink or toner. The halftone signal is derived by comparing a given value, which is a combined value of a grayscale value of a pixel and a cumulative error from previously processed pixels, with a predefined threshold value. The difference between the given value and the halftone value is the halftoning error. By distributing the halftoning errors, the density of dark pixels will be determined by the grayscale values from a number of surrounding pixels. Consequently, regions of the digital image having lighter shades of grayscale will yield lower densities of dark pixels, while regions having darker shades of grayscale will yield higher densities of dark pixels. In this fashion, digital images having more than two shades of grayscale can be printed using a binary printer.
In FIG. 1, a conventional system 10 that executes error diffusion halftoning is shown. The system includes an input device 12, an error diffusion halftoning (EDH) device 14, and a binary output device 16. The input device provides a digital image that is to be printed by the binary output device. The input device may be a scanner that can capture the digital image from a photograph, a digital camera that can capture the digital image from an actual scene, or a storage device that can receive the digital image from an external source. The error diffusion device includes a summing unit 18, a thresholding module 20, a subtraction unit 22, an error diffuser 24, and an error buffer module 26.
In operation, the system 10 processes the digital image by sequentially operating on the image pixels of the digital image in a raster scan order, which is a left-to-right, top-to-bottom sequence. For each pixel of the image, a grayscale value gi,j of that pixel is transmitted from the input device 12 to the summing unit 18 of the EDH device 14, where gi,j xcex5[0,255] for 256 grayscale. The values i and j identify the row and column, respectively, of the current pixel being processed. The summing unit 18 combines the grayscale value gi,j with a final error ei,j and outputs a summed value si,j. The final error ei,j is derived from halftoning errors associated with the previous pixels that were processed by the EDH device. The summed value si,j is then transmitted to the thresholding module 20 and the subtraction unit 22. The thresholding module compares the summed value si,j to a threshold value, e.g., 127 for 256 grayscale. The comparison produces an output halftone value hi,j, which is one of two values, e.g., 0 or 255. If the summed value si,j is less than the threshold value, the output halftone value hi,j equates to a first value, e.g., 0, that directs the output device 16 to refrain from depositing ink or toner. However, if the summed value si,j is equal to or greater than the threshold value, the output halftone value hi,j equates to a second value, e.g., 255, that directs the output device to deposit the ink or toner.
The output halftone value hi,j is also transmitted to the subtraction unit 22 to derive a halftoning error that results from converting the summed value si,j into one of two halftone values. The subtraction unit subtracts the halftone value hi,j from the summed value si,j. The result of this operation is a halftoning error ni,j, which is transmitted to the error diffuser 24. The error diffuser then divides the halftoning error ni,j using a known distribution process, such as the Floyd-Steinberg error diffusing process. The divided halftoning errors are transmitted to the error buffer module 26. The error buffer module processes the divided halftoning errors, such that each divided halftoning error can be diffused into a neighboring pixel of the current pixel. These divided halftoning errors are combined with other divided halftoning errors from previously processed pixels to form final errors that are to be diffused into subsequently processed pixels. The final errors are temporarily stored in an error buffer (not shown) within the error buffer module. The error buffer has a capacity to store the final errors for an entire row of image pixels. For 256 grayscale, each bin of the primary error buffer is an 8-bit bin. When the grayscale value gi,j+1 of the next pixel is processed, a final error ei,j+1 stored in the bin of the error buffer associated with that pixel is transmitted to the summing unit 18. This final error is combined with the grayscale value gi,j+1 and the above-described process is repeated. In this fashion, the halftoning errors from the pixels of the digital image are distributed to reproduce the digital image as a halftone image using the binary output device 16.
Although conventional error diffusion halftoning systems, such as the system 10, operate well for their intended purpose, what is needed is a cost-efficient error diffusion system and a method of managing errors in such a system.
An error diffusion halftoning system and a method of managing halftoning errors utilize a quantization technique to reduce the required size of a primary error buffer that is needed to diffuse the halftoning errors. By implementing the quantization technique, the primary error buffer can be reduced from an 8-bits-per-bin error buffer to a 2-bits-per-bin error buffer for 256 grayscale. The reduction in bin size decreases the cost of the primary error buffer and, consequently, the cost of an error diffusion halftoning (EDH) device of the system that generates halftone signals from grayscale values of a digital image.
The error diffusion halftoning system includes an input device, the EDH device, and a binary output device. The input device may be a digital scanner, a digital camera, or a storage device that can acquire digital images. The binary output device may be a conventional inkjet or laser printer. The EDH device is operatively connected to the input device and the binary output device to process grayscale pixel values of a given digital image from the input device, generating halftone signals, and to transmit the generated halftone signals to the binary output device. The halftone signals are used by the binary output device to decide whether to deposit or to refrain from depositing ink or toner in order to print a halftone image in accordance with the given digital image. In addition, the EDH device operates to manage the halftoning errors that are produced from the generation of the halftone signals.
The EDH device includes a summing unit, a thresholding module, a subtraction unit, an error diffuser, and a quantization-error diffusion (QED) module. The summing unit is positioned to receive a grayscale value from the input device and a corresponding final error from the QED module for each pixel being processed by the EDH device. The final error contains halftoning errors and quantization errors from previously processed grayscale values. The halftoning errors are the resulting products of a thresholding operation executed by the thresholding module, while the quantization errors are the resulting products of a quantization operation executed by the QED module. The summing unit combines the received grayscale value and the received final error to produce a summed value, which is transmitted to the thresholding module and the subtraction unit.
After the summed value is received by the thresholding module, the summed value is thresholded by the thresholding module using a predefined threshold value to generate a halftone signal. The halftone signal is then transmitted to the binary output device to control the depositing operation of the output device. The halftone signal is also transmitted to the subtraction unit, where the summed value from the summing unit is subtracted by the halftone signal to derive a halftoning error. The halftoning error is used by the error diffuser to distribute portions of the halftoning error to different components of the QED module, so that the portions of the halftoning error can be diffused to unprocessed pixels that are adjacent to the current pixel being processed. In the preferred embodiment, the error diffuser is configured to generate four apportioned halftoning errors from the halftoning error using a Floyd-Steinberg scheme. That is, the halftoning error is multiplied using parameters a, b, c and d, where a={fraction (3/16)}, b={fraction (5/16)}, c={fraction (1/16)} and d={fraction (7/16)}. However, the error diffuser may be configured to generate the four apportioned halftoning errors using a different set of parameters. In an alternative embodiment, the error diffuser may be configured to generate any number of apportioned halftoning errors using a corresponding number of predefined parameters.
The QED module operates to manage the apportioned halftoning errors for each pixel of the digital image being processed. The apportioned halftoning errors from different pixels are combined by the QED module and added to selected pixels when these pixels are processed by the EDH device.
The QED module includes the primary error buffer, an intermediate error buffer, a supplemental error buffer, a quantization unit, a de-quantization unit, and three weighting units. The primary error buffer includes a number of bins. Each bin of the primary error buffer has a capacity to store 2-bit information. The number of bins included in the primary error buffer is not critical to the invention. However, the primary error buffer contains a sufficient number of bins to store error information for an entire pixel row of a typical digital image that is to be processed by the system. The intermediate error buffer is a 3-bin buffer that can temporarily store three apportioned halftoning errors from the error diffuser. Similarly, the supplemental error buffer is a single bin buffer that can temporarily store the remaining apportioned halftoning error from the error diffuser. Notice that the number of bins in the intermediate and supplemental error buffers is the number of error terms to which the error is diffused. These numbers are equal to four in the present case, but may be greater or less. The intermediate and supplemental error buffers are of size 8 or more bits per bin. The intermediate error buffer is configured such that when the next pixel is processed, values stored in the bins are shifted to the left. The stored value in the far left bin of the intermediate error buffer, however, is transmitted to the quantization unit of the QED module. This configuration allows apportioned halftoning errors from different pixels to be combined and stored within the bins of the intermediate error buffer.
The quantization unit is configured to convert the stored value in the left bin of the supplemental error buffer into a quantized value using a predefined quantization table. The operation of the quantization unit produces a quantization error, which is diffused in a manner similar to the diffusion of the halftoning error. In one embodiment, the quantization error is apportioned by the three weighting units using predefined multiplicative parameters to produce three apportioned quantization errors. One of the apportioned quantization errors is transmitted to the supplemental error buffer, while the two remaining apportioned quantization errors are transmitted to the middle and right bins of the intermediate error buffer. In another embodiment, the entire quantization error is combined with an apportioned halftoning error and transmitted to the supplemental error buffer, so that the quantization error can be introduced to the grayscale value of a pixel that is to be processed next.
The de-quantization unit of the QED module is coupled to the primary error buffer. When a grayscale value of a pixel is received by the EDH device, a quantized value that corresponds to that pixel is extracted from a bin of the primary error buffer. The quantized value is then expanded by the de-quantization unit using a predefined de-quantization table. The de-quantized value is combined with a stored value in the supplemental error buffer, resulting in a final error. The final error is then added to the grayscale value of the pixel being processed to derive a summed value that will be used to generate the halftone signal. In this manner, the halftoning errors and the quantization errors of previously processed pixels are diffused to grayscale values of subsequently processed pixels.